class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        self.word = word
        self.m = len(board)
        self.n = len(board[0])
        
        for i in range(self.m):
            for j in range(self.n):
                if board[i][j] == word[0]:
                    self.visited = [[False for _ in range(self.n)] for _ in range(self.m)]
                    self.board = board
                    self.index = 1
                    if self.backtacking(i,j): return True
        return False
    
    def backtacking(self,col,row):
        if self.index == len(self.word):
            return True
        for nx,ny in [(-1,0),(1,0),(0,1),(0,-1)]:
            ncol = col + nx
            nrow = row + ny
            if ncol < 0 or ncol >= self.m: continue
            if nrow < 0 or nrow >= self.n: continue 
            if self.board[ncol][nrow] != self.word[self.index]:
                continue
            self.visited[ncol][nrow] = True
            self.index += 1
            if self.backtacking(ncol,nrow):
                return True
            self.index -= 1
            self.visited[ncol][nrow] = False
        return False
            
s = Solution()
s.exist(board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB")